#include <stdio.h>
#include <stdlib.h>

#define NUM 9

typedef struct node{
	int data;
	struct node *next;
} node_t;

void insert_node(node_t **head, int data)
{
	node_t *new = (node_t *)malloc(sizeof(node_t));
	new->data = data;

	if (!*head)
		*head = new;
	else {
		new->next = *head;
		*head = new;
	}
}

inline void print_list(node_t *p)
{
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

void do_sort(node_t **h, node_t *end)
{
	node_t *pre, *p, *next, *pos;
	int v;

	if (*h == NULL || *h == end || (*h)->next == end)
		return;
	pre = *h;
	pos = *h;
	p = (*h)->next;
	v = (*h)->data;

	while (p != end) {
		next = p->next;
		if (p->data < v) {
			pre->next = next;
			p->next = *h;
			*h = p;
		} else {
			pre = p;
		}
		p = next;
	}
	do_sort(h, pos);
	do_sort(&(pos->next), end);
}

void quick_sort(node_t **h)
{
	do_sort(h, NULL);
}

int main()
{
	node_t *head = NULL;
	int i, data[NUM] = {9, 7, 4, 8, 3, 2, 1, 6, 5} ;

	for (i = 0; i < NUM; i++)
		insert_node(&head, data[i]);
	print_list(head);

	quick_sort(&head);
	print_list(head);
	
	return 0;
}

